package com.yinxin.wudasuanfa.dongtaiguihua;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yinxin
 * @version 1.0
 * @Description:
 * @date 2022/5/614:09
 */
public class Exercise3 {
    public static void main(String[] args) {
        int[] nums = {2, 3, 4};
        System.out.println(subsets(nums));
    }

    public static List subsets(int[] nums) {
    // //结果集合
    // List> list = new ArrayList();
    // //回溯⽅法
    // backtrack(list,new ArrayList<>(),nums);
    // return list;
        //⼀个全局变量，⽤于保存所有集合
        List list = new ArrayList<>();
        //传⼊三个参数，没有附加参数
        backtrack(list, new ArrayList<>(), nums);
        return list;
    }

    public static void backtrack(List list, List tempList, int[] nums) {
        //终结条件
        if (tempList.size() == nums.length) {
            //全局变量添加⼀个满⾜条件的集合
            list.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tempList.contains(nums[i])) {
                    continue;
                }
                //如果tempList没有包含nums[i]才添加
                tempList.add(nums[i]);
                //递归调⽤，此时的tempList⼀直在变化，直到终结条件才结束
                backtrack(list, tempList, nums);
                //System.out.println("tempList的内容:" + tempList + "-------" + "i的值:" + i);
                //移除掉最后⼀个元素的作⽤就是返回到上⼀次调⽤时的数据，也就是希望返回之前的节点再去重新搜索满⾜条件，这样才能实现回溯
                tempList.remove(tempList.size() - 1);
            }
        }
    }

}
